package ai.zixing.mashibing.advance_class.first.class05;

/**
 * 末尾添加最短字符串使其变为回文
 */
public class Code02_AddShortestEnd {

    private static String shortestEnd(String str) {
        if (str == null || str.isEmpty()) {
            return null;
        }
        char[] arr = manacherString(str);
        int[] pArr = new int[arr.length];
        int R = -1;
        int C = -1;
        int maxContainsEnd = -1;
        for (int i = 0; i < arr.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < arr.length && i - pArr[i] > -1) {
                if (arr[i + pArr[i]] == arr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (pArr[i] + i > R) {
                R = pArr[i] + i;
                C = i;
            }
            if (R == arr.length) {
                maxContainsEnd = pArr[i];
                break;
            }
        }
        char[] res = new char[str.length() - maxContainsEnd + 1];
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = arr[i * 2 + 1];
        }
        return String.valueOf(res);
    }

    private static char[] manacherString(String string) {
        char[] str = string.toCharArray();
        char[] ans = new char[str.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (i & 1) == 0 ? '#' : str[index++];
        }
        return ans;
    }

    public static void main(String[] args) {
        String str1 = "abcd123321";
        System.out.println(shortestEnd(str1));
    }
}
